// queuetp.h -- queue template with a nested class
#ifndef STARTCPP_QUEUETP_H
#define STARTCPP_QUEUETP_H 0x10

template<class Item>
class QueueTP {
private:
    enum {
        Q_SIZE = 10
    };

    // Node is a nested class definition
    class Node {
    public:
        Item item;
        Node *next;
        Node(const Item &i) : item(i), next(nullptr) {}
    };

    Node *front;       // pointer to front of Queue
    Node *rear;        // pointer to rear of Queue
    int items;          // current number of items in Queue
    const int qsize;    // maximum number of items in Queue
    QueueTP(const QueueTP &q) : qsize(0) {}

    QueueTP &operator=(const QueueTP &q) { return *this; }

public:
    QueueTP(int qs = Q_SIZE);

    ~QueueTP();

    bool isempty() const {
        return items == 0;
    }

    bool isfull() const {
        return items == qsize;
    }

    int queuecount() const {
        return items;
    }

    // add item to end
    bool enqueue(const Item &item);

    // remove item from front
    bool dequeue(Item &item);
};

template<class Item>
QueueTP<Item>::QueueTP(int qs) :qsize(qs) {
    front = rear = 0;
    items = 0;
}

template<class Item>
QueueTP<Item>::~QueueTP() {
    Node *temp;
    while (front != 0)  // while queue is not yet empty
    {
        temp = front;   // save address of front item
        front = front->next;    // reset pointer to next item
        delete temp;
    }
}

template<class Item>
bool QueueTP<Item>::enqueue(const Item &item) {
    if (isfull())
        return false;
    Node *add = nullptr;
    try {
        *add = new Node(item); // create Map
    } catch (std::bad_alloc &e) {
        return false;
    }
    // on failure, new throws std::bad_alloc exception
    ++items;
    if (front == 0)         // if queue is empty,
        front = add;        // place item at front
    else
        rear->next = add;   // else place at rear
    rear = add;     // have rear point to new Map
    return true;
}

template<class Item>
bool QueueTP<Item>::dequeue(Item &item) {
    if (front == 0)
        return false;
    item = front->item;     // set item to first item in queue
    --items;
    Node *temp = front;     // save location of first item
    front = front->next;    // reset front to next item
    delete temp;            // delete former first item
    if (items == 0)
        rear = 0;
    return true;
}

#endif //STARTCPP_QUEUETP_H
